package com.cskaoyan.javase.recursion._1basic;

/**
 * 递归的思想与危险的递归
 * 引例：使用递归计算N（N>=1）的阶乘（factorial）
 * n! = n * (n -1) * (n-2) * ...* 1;
 *
 * 以上求解阶乘,实际上也可以用循环去完成
 * 在使用循环求解问题时,要找到重复执行的代码是什么,也就是说要找到循环体
 * n的阶乘,相当于累乘,但是每乘一次,被乘的数就要减一
 *
 * 那么使用递归求解问题的核心思路是什么呢?
 * 我们把方法在运行时调用自身的情况，称之为递归，又叫做递归调用。
 * 所以递归求解问题的方式,是使用一样的方式解决问题,但是每次都让问题的规模更小
 * 最终让问题的规模小到可以直接运算
 * 这种分解的思想,就是递归求解的核心思想.
 * 这种将大问题分解为小问题的思想就是递归的思想：
 *      1.把一个复杂的大规模的问题，分解成若干相似的小规模的子问题。
 *          (递归体)
 *      2.当子问题规模足够小的时候，就可以直接得到小规模问题的解。
 *          (递归的出口)
 *      3.然后把所有的小规模的子问题的解，组合起来，得到要求解的大规模问题的解。
 *
 * 分解n的阶乘这个问题,并且分解后解决问题的思路是不变的,变成相似的小规模问题:
 * n! = n * (n -1) * (n-2) * ...* 1;
 * n! = n * (n-1)!
 * (n-1)! = (n-1) * (n-2)!
 * ...
 * 1! = 1
 * 设n!是f(n),那么:
 *      f(n) = n * f(n-1) 递归的递归体
 *      f(1) = 1 递归的出口
 *
 * 递归的优缺点:
 * 不难发现递归的优点是：
 *      1.递归的代码会非常简洁，这是最直观的。
 *      2.人在解决问题的时候，都会下意识的分解问题。
 *          递归的思想很符合人的思维，用递归求解一个问题的思路很容易被人理解。
 *          一个问题,一旦能够找打分解问题的思路，递归会非常好用,非常易于理解.
 * 当然递归的缺点也非常明显：
 *      1.栈溢出错误警告！递归很危险，一旦栈溢出是严重错误！而且栈溢出严格来说,几乎无法避免.
 *      2.不用递归时，往往一个方法调用就能解决问题。
 *      而递归会调用多个方法，占用大量栈内存，且明显存在重复计算，效率低。
 *      也就是说，使用递归求解一个问题，既耗费资源,效率也非常低
 *      时间和空间复杂度都不占优势，既占用空间效率还低。
 *
 * 实际上，递归是现代计算机出现以后,借助了计算机庞大的算力而产生的一种暴力求解问题的解决方式,优点是比较好想,缺点就是慢.
 *
 * 一把伤人亦伤己的利器，实际开发中不要随意使用递归
 * 使用递归要深思熟虑递归的深度和出口，避免栈溢出错误
 *
 * @since 15:40
 * @author wuguidong@cskaoyan.onaliyun.com
 */
public class Demo {
    public static void main(String[] args) {
        System.out.println(factorialLoopSolution(10));
        System.out.println(factorialRecursionSolution(10));
    }

    // 递归求解n的阶乘
    public static long factorialRecursionSolution(int n) {
        if (n == 1) {
            return 1;
        }
        return n * factorialRecursionSolution(n - 1);
    }

    // 循环求解n的阶乘
    public static long factorialLoopSolution(int n) {
        // 预先定义乘积结果,初始值1
        long product = 1;
        // 把循环中的i当成每次循环乘以的数
        for (int i = n; i > 0; i--) {
            // 循环i次,实际上就是循环n次,乘了n次
            product *= i;
        }
        return product;
    }
}
